package com.yanceysong.codetop.s31_s40;

import com.yanceysong.common.ListNode;


public class S35_Mid_82_删除排序链表中的重复元素_II {
    /**
     * S35_Mid_82_删除排序链表中的重复元素_II
     * LeetCode题目链接: <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/">...</a>
     * ----------------------------------------------------------------------
     * 题目描述:
     * 给定一个已按非递减顺序排序的链表 head，删除所有存在重复数字的节点，只留下所有 原始链表中只出现一次 的数字。
     * 返回 处理后的链表（同样有序）。
     * ----------------------------------------------------------------------
     * 示例 1:
     * 输入: head = [1,2,3,3,4,4,5]
     * 输出: [1,2,5]
     * 解释: 数值 3 和 4 出现多次，应整体移除。
     * <p>
     * 示例 2:
     * 输入: head = [1,1,1,2,3]
     * 输出: [2,3]
     * <p>
     * 示例 3:
     * 输入: head = [1,1]
     * 输出: []
     * <p>
     * 示例 4:
     * 输入: head = [1,2,2]
     * 输出: [1]
     * ----------------------------------------------------------------------
     * 关键要求/注意点:
     * 1. 链表已排序: 相同的重复值必定是连续段，可一次性整体跳过。
     * 2. "删除重复节点" 的含义是: 如果某个值出现次数 > 1，则所有该值的节点都不保留。
     * 3. 需要小心处理链表头本身就是重复段的情况，因此常用 "哨兵节点"(dummy/sentinel) 统一逻辑。
     * ----------------------------------------------------------------------
     * 解题思路(双指针遍历 + 跳过重复段):
     * 1. 创建一个哨兵节点 sentinelHead，其 next 指向 head；定义指针 scan 初始指向 sentinelHead。
     * 2. 维持循环条件 scan.next != null && scan.next.next != null，这样可以安全比较相邻两个节点的值。
     * 3. 若 scan.next.val == scan.next.next.val，说明出现了一个重复段：
     * .     - 记录该重复值 duplicateVal = scan.next.val
     * .     - 继续 while (scan.next != null && scan.next.val == duplicateVal) 扫描并跳过所有这一段的节点。
     * .     - 跳过后，scan 仍指向重复段前的最后一个合法节点，它的 next 已经连接到下一个不同值（或null）。
     * .   否则，若不重复，则 scan = scan.next 正常前进。
     * 4. 遍历结束返回 sentinelHead.next。
     * ----------------------------------------------------------------------
     * ASCII 图示 (示例: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5):
     * . 初始:  S -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null   (S 为哨兵)
     * . 扫描到 "3 3" 重复:
     * . 跳过所有 3:  S -> 1 -> 2 -> 4 -> 4 -> 5 -> null
     * . 再扫描到 "4 4" 重复:
     * . 跳过所有 4:  S -> 1 -> 2 -> 5 -> null
     * . 返回 S.next 即 1 -> 2 -> 5
     * ----------------------------------------------------------------------
     * 复杂度分析:
     * . - 时间复杂度: O(n)  每个节点至多被访问/跳过一次。
     * . - 空间复杂度: O(1)  仅使用常数额外指针。
     * ----------------------------------------------------------------------
     * 关键洞察/易错点:
     * 1. 使用哨兵节点避免头部就是重复段时丢失头引用的麻烦。
     * 2. 跳过重复段时外层指针 scan 不前进，只更新其 next 指针到第一个不同值位置。
     * 3. while 内部跳过重复段时每次重新检查 scan.next != null，防止 NPE。
     * 4. 不能只删除部分重复节点，要删除重复值的整段。
     * ----------------------------------------------------------------------
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 哨兵节点，简化头节点可能被删除的逻辑
        ListNode sentinel = new ListNode(0, head);
        // prev 指向有效链表的最后一个节点
        ListNode prev = sentinel;
        // cur 指向当前待检查的节点
        ListNode cur = head;

        while (cur != null) {
            // 检查 cur 是否为重复段的开头
            if (cur.next != null && cur.val == cur.next.val) {
                // 是重复段，则一直向后找到这个重复段的末尾
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // cur 现在是重复段的最后一个节点，整个段都应被删除
                // prev.next 直接连接到重复段之后的第一个节点
                prev.next = cur.next;
            } else {
                // cur 不是重复节点，prev 和 cur 都正常前进
                prev = prev.next;
            }
            // cur 前进到下一个待检查的节点
            cur = cur.next;
        }
        return sentinel.next;
    }

    // ---------------------------- 以下为测试代码 & 辅助函数 ----------------------------
    public static void main(String[] args) {
        S35_Mid_82_删除排序链表中的重复元素_II solver = new S35_Mid_82_删除排序链表中的重复元素_II();
        System.out.println("=== 删除排序链表中的重复元素 II 测试开始 ===\n");

        testExample1(solver);        // 示例1
        testExample2(solver);        // 示例2
        testAllDuplicate(solver);    // 全部重复
        testNoDuplicate(solver);     // 无任何重复
        testHeadDuplicate(solver);   // 头部整段重复
        testTailDuplicate(solver);   // 尾部整段重复
        testSingleNode(solver);      // 单节点
        testTwoDifferent(solver);    // 两个不同节点
        testTwoSame(solver);         // 两个相同节点 -> 空
        testInterleaved(solver);     // 交错重复块

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void testExample1(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试1] 输入: [1,2,3,3,4,4,5]");
        ListNode head = build(1, 2, 3, 3, 4, 4, 5);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 1->2->5");
        assert listEquals(result, build(1, 2, 5));
    }

    private static void testExample2(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试2] 输入: [1,1,1,2,3]");
        ListNode head = build(1, 1, 1, 2, 3);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 2->3");
        assert listEquals(result, build(2, 3));
    }

    private static void testAllDuplicate(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试3] 输入: [5,5,5,5]");
        ListNode head = build(5, 5, 5, 5);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: <空>");
        assert result == null;
    }

    private static void testNoDuplicate(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试4] 输入: [1,2,3,4,5]");
        ListNode head = build(1, 2, 3, 4, 5);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 1->2->3->4->5");
        assert listEquals(result, build(1, 2, 3, 4, 5));
    }

    private static void testHeadDuplicate(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试5] 输入: [1,1,2,3]");
        ListNode head = build(1, 1, 2, 3);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 2->3");
        assert listEquals(result, build(2, 3));
    }

    private static void testTailDuplicate(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试6] 输入: [1,2,3,3]");
        ListNode head = build(1, 2, 3, 3);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 1->2");
        assert listEquals(result, build(1, 2));
    }

    private static void testSingleNode(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试7] 输入: [7]");
        ListNode head = build(7);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 7");
        assert listEquals(result, build(7));
    }

    private static void testTwoDifferent(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试8] 输入: [1,2]");
        ListNode head = build(1, 2);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 1->2");
        assert listEquals(result, build(1, 2));
    }

    private static void testTwoSame(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试9] 输入: [8,8]");
        ListNode head = build(8, 8);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: <空>");
        assert result == null;
    }

    private static void testInterleaved(S35_Mid_82_删除排序链表中的重复元素_II solver) {
        System.out.println("[测试10] 输入: [1,1,2,3,3,4,5,5,6]");
        ListNode head = build(1, 1, 2, 3, 3, 4, 5, 5, 6);
        ListNode result = solver.deleteDuplicates(head);
        print(result, "期望: 2->4->6");
        assert listEquals(result, build(2, 4, 6));
    }

    // 构造链表的工具函数（按顺序创建）
    private static ListNode build(int... vals) {
        if (vals == null || vals.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : vals) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    // 打印链表（测试输出显示）
    private static void print(ListNode head, String hint) {
        StringBuilder sb = new StringBuilder();
        ListNode cur = head;
        while (cur != null) {
            sb.append(cur.val);
            if (cur.next != null) sb.append("->");
            cur = cur.next;
        }
        String content = sb.isEmpty() ? "<空>" : sb.toString();
        System.out.println("输出: " + content + " | " + hint);
    }

    // 判断两链表结构与顺序是否相同
    private static boolean listEquals(ListNode a, ListNode b) {
        while (a != null && b != null) {
            if (a.val != b.val) return false;
            a = a.next;
            b = b.next;
        }
        return a == null && b == null;
    }
}
